We present H-band images obtained with NICMOS of a field 75'' (5kpc) above the plane of the disk of the edge-on spiral galaxy NGC 5907. Ground-based observations have shown that NGC 5907 has a luminous halo with a shallow radial profile between 4 and 8 kpc that roughly traces the dark matter distribution of the galaxy deduced from its rotation curve. Our NICMOS observations were designed to resolve bright giants in the halo of NGC 5907 to constrain its stellar composition with the goal of understanding its nature and origin. More than 100 stars are expected in the NICMOS images if the dwarf-to-giant ratio in the halo of NGC 5907 is consistent with that expected from standard stellar initial mass functions, and if ground-based estimates of the distance to NGC 5907 and the integrated colors of its halo are correct. Instead we observe only one candidate giant star. This apparent discrepancy can be resolved by assuming either a significantly larger distance than suggested by several studies, or a halo metallicity much lower than suggested by ground-based colors and as low as metal-poor Galactic globular clusters. If previous distance and halo color estimates for NGC 5907 are correct, our NICMOS results suggest that its extended light is composed of stars that formed with an initial mass function different than that observed locally, leading to a much higher ratio of dwarfs to giants. We describe how these three possible explanations for the absence of bright giants in our NICMOS images of the halo of NGC 5907 might be constrained by future observations.